package interview.powerset;

import java.util.ArrayList;
import java.util.Stack;

public class PowerSet {
	public void powerset1(String source) {
		powersetRecursive(source.toCharArray(), source.length(), "");
	}
	
	public void powerset2(String source) {
		powersetIterative(source.toCharArray(), source.length());
	}
	
	public void powerset3(String source) {
		boolean[] flags = new boolean[source.length()];
		powersetRecursive2(source.toCharArray(), flags, -1);
	}
	
	public void powerset4(String source) {
		powersetIterative2(source.toCharArray(), source.length());
	}

	private void powersetIterative2(char[] charArray, int length) {
		Stack<Boolean> stack = new Stack<Boolean>();
		StringBuilder buffer = new StringBuilder();
		
		while(stack.size() < length) {
			stack.push(true);
			buffer.append(charArray[stack.size() - 1]);
		}
		
		while(true) {
			if(stack.size() == length) {
				System.out.println(buffer.toString());
			}
			
			while(!stack.empty() && !stack.peek()) {
				stack.pop();
			}
			
			if(stack.empty()) {
				break;
			}
			
			buffer.setLength(buffer.length() - 1);
			stack.pop();
			stack.push(false);
			
			while(stack.size() < length) {
				stack.push(true);
				buffer.append(charArray[stack.size() - 1]);
			}
		}	
	}

	private void powersetRecursive2(char[] charArray, boolean[] flags, int level) {
		if(level == charArray.length - 1) {
			for(int i = 0; i < flags.length; i++) {
				if(flags[i]) {
					System.out.print(charArray[i]);
				}
			}
			System.out.println();
			return;
		}
		
		powersetRecursive2(charArray, flags, level + 1);
		flags[level + 1] = true;
		powersetRecursive2(charArray, flags, level + 1);
		flags[level + 1] = false; 
	}

	private void powersetRecursive(char[] charArray, int length, String suffix) {
		if(length == 0) {
			System.out.println(suffix);
			return;
		}
		
		powersetRecursive(charArray, length - 1, suffix);
		powersetRecursive(charArray, length - 1, charArray[length - 1] + suffix);
	}
	
	private void powersetIterative(char[] charArray, int length) {
		ArrayList<String> temp1 = new ArrayList<String>();
		ArrayList<String> temp2 = new ArrayList<String>();
		ArrayList<String> powerset, buffer, tmp;
		powerset = temp1;
		buffer = temp2;
		for(int i = 0; i < length; i++) {
			if(powerset.isEmpty()) {
				powerset.add("");
				powerset.add(charArray[i] + "");
			} else {
				for(String s : powerset) {
					buffer.add(s + charArray[i]);
					buffer.add(s);
				}
				tmp = powerset;
				powerset = buffer;
				buffer = tmp;
				buffer.clear();
			}
		}
		
		for(String s : powerset) {
			System.out.println(s);
		}
	}
}
